Przekątne [B]

Limit pamięci: 256 MB

Mamy dany wielokąt foremny o wierzchołkach. Wybieramy jego przekątnych. Chcielibyśmy sprawdzić, czy któraś para wybranych przekątnych się przecina (oczywiście nie licząc przecięć w wierzchołkach wielokąta).

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis wielokąta i wybranych przekątnych,
• sprawdzi, czy jakakolwiek para spośród wybranych przekątnych wielokąta się przecina, a jeżeli tak, to znajdzie taką przykładową parę,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające liczbę wierzchołków wielokąta foremnego oraz liczbę wybranych przekątnych tego wielokąta. Kolejne wierszy zawiera po dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające przekątną wielokąta, łączącą wierzchołki o numerach oraz (wierzchołki wielokąta numerujemy liczbami od do w kolejności obchodzenia obwodu wielokąta przeciwnie do kierunku ruchu wskazówek zegara). Można założyć, że każda para numerów wierzchołków na wejściu definiuje poprawnie przekątną wielokąta (a nie np. bok czy wierzchołek). Przekątne podane na wejściu będą parami różne.

Wyjście

Pierwszy i jedyny wiersz wejścia powinien zawierać:

• jedno słowo NIE, jeżeli żadna para podanych przekątnych się nie przecina albo
• dwie różne liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające numery przekątnych, które się przecinają; jeżeli istnieje więcej niż jedna poprawna odpowiedź, należy wypisać dowolną z nich. Przekątne numerujemy zgodnie z kolejnością występowania na wejściu.

Przykład

Dla danych wejściowych:

6 4
3 6
1 4
6 2
2 5

poprawną odpowiedzią jest:

2 3

natomiast dla danych:

6 2
1 3
1 5

poprawnym wynikiem jest:

NIE

Na rysunku ciągłą linią zaznaczono przekątne z pierwszego testu, natomiast przerywaną linią - przekątne z drugiego testu.